import math

from models.graph import OneDimensionalGraph

def testCDS(number_vertices):
    g = OneDimensionalGraph(number_vertices)

    # print "vertices:"
    # for vertex in g.getVertices():
    #     print "%.3f"% (vertex,),
    # print

    cds = g.findConnectedDominatingSet()
    # print "CDS:"
    # for dom_vertex in cds:
    #     print "%.3f"% (dom_vertex,),
    # print

    print "Coverage:", g.getCoverage()
    print "Size of constructed CDS:\t", len(cds)
    print "Lower bound of CDS size:\t", int(math.ceil(g.getCoverage()/g.getRadius() - 3))
    print "Expected value of lower bound:\t", math.sqrt(2*number_vertices) - 3